home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 3669 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  3.2 KB
  1. Path: ibm32.perftech.com!usenet
  2. From: murf@perftech.com (John Murphy)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Sorting large files
  5. Date: 30 Jan 1996 16:38:44 GMT
  6. Organization: Performance Technology Inc
  7. Message-ID: <4elhik$cpq@ibm32.perftech.com>
  8. References: <4e8j9b$cuf@longwood.cs.ucf.edu>
  9. NNTP-Posting-Host: k5zba.perftech.com
  10. Mime-Version: 1.0
  11. NNTP-Posting-User: REVCO
  12. X-Newsreader: WinVN 0.93.11
  13.  
  14. In article <4e8j9b$cuf@longwood.cs.ucf.edu>, schnitzi@longwood.cs.ucf.edu 
  15. says...
  16. >
  17. >There was some discussion here a little while
  18. >back on how to sort the lines in a large file
  19. >without having to have a huge character array.
  20. >I suggested using ftell and fseek to hunt down
  21. >the particular lines you are comparing.  Only
  22. >just the other day did I notice (via a web
  23. >search engine) that someone posted a question
  24. >on how this could be done...  So here goes.
  25. >
  26. >
  27. >This program sorts stdin to stdout, so it would
  28. >have to be run like this:
  29. >
  30. >        sort < infile > outfile
  31. >
  32. >It should be easy enough to modify to use file
  33. >pointers, though.  It also requires a 'long'
  34. >for every line in the file, but this beats the
  35. >heck out of a huge character array.  I've 
  36. >written it here to handle up to 5000-line files.
  37. >
  38. >
  39. >#include <stdio.h>
  40. > 
  41. >main()
  42. >{
  43. >        long index[5000], z;
  44. > 
  45. >        char line1[ 256 ], line2[ 256 ];
  46. > 
  47. >        int i, j, count=0;
  48. > 
  49. >        do
  50. >        {
  51. >                index[ count++ ] = ftell( stdin );
  52. >        }
  53. >        while ( gets(line1) );
  54. > 
  55. >        for ( i=0; i<count-1; i++ )
  56. >        {
  57. >                for ( j=i+1; j<count; j++ )
  58. >                {
  59. >                        fseek( stdin, index[i], 0 );
  60. >                        gets( line1 );
  61. >                        fseek( stdin, index[j], 0 );
  62. >                        gets( line2 );
  63. > 
  64. >                        if ( strcmp( line1, line2 ) > 0 )
  65. >                        {
  66. >                                z = index[i];
  67. >                                index[i] = index[j];
  68. >                                index[j] = z;
  69. >                        }
  70. >                }
  71. >        }
  72. > 
  73. >        for ( i=0; i<count; i++ )
  74. >        {
  75. >                fseek( stdin, index[i], 0 );
  76. >                gets( line1 );
  77. >                puts( line1 );
  78. >        }
  79. >}
  80. >
  81. Who says computer people don't have a sense of humor?!
  82.  
  83. Least any neophytes miss the joke and take this as a serious solution to the
  84. sorting problem, perhaps we should point out that while this code will
  85. compile and run and even (eventually) sort a file, it's practical use will
  86. be limited by the MTBF of your equipment and/or your life expectancy ---
  87. it's SLOOOW!  Any file I/O operation is time consuming, and depending on the
  88. file system, random file I/O can be VERY time consuming; with MS-DOS, for
  89. instance, reading a large file backwards is an N-squared operation.
  90.  
  91. As a sanity check on the practicality of this method of sorting, try sorting
  92. a 20,000 byte file; that's a file that would require the same amount of
  93. memory as the array of 5000 longs.  On one of my systems, using this code to
  94. sort a file of 250 80 bytes records took 17:30 minutes; sorting the same
  95. file with MS-DOS SORT (a very slow sort program) took 0.8 seconds.
  96.  
  97. The trick to sorting large files in a reasonable amount of time is to
  98. minimize the file I/O.  As usual, see Knuth for details...
  99.  
  100. Murf
  101.  
  102.